package huaweiod.first;

/**
 * 华为OD机试真题 Java 实现【找出重复代码】【2022.11 Q4 新题】
 */
public class A_2023_50_FindRepeatSubstring {

    // 1、暴力解
    public static String findRepeatSubstring1(String s1, String s2) {
        String longStr = s1.length() >= s2.length() ? s1 : s2;
        String shortStr = s1.length() < s2.length() ? s1 : s2;
        String ans = "";
        int len;
        for (int i = 0; i < shortStr.length(); i++) {
            len = shortStr.length();
            for (int j = len; j > i; j--) {
                if (j - i <= ans.length()) {
                    break;
                }
                String temp = shortStr.substring(i, j);
                if (longStr.contains(temp)) {
                    ans = temp;
                    break;
                }
            }
        }
        return ans;
    }

    // 2、动态规划
    public static String findRepeatSubstring(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        int maxLen = 0;
        int position = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    if (dp[i + 1][j + 1] > maxLen) {
                        maxLen = dp[i + 1][j + 1];
                        position = i;
                    }
                }
            }
        }
        if (maxLen == 0) {
            return "";
        } else {
            return s1.substring(position - maxLen + 1, position + 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(findRepeatSubstring("hello123world1", "hello123abc4"));   // hello123
        System.out.println(findRepeatSubstring("private_void_method", "public_void_method"));   // _void_method
        System.out.println(findRepeatSubstring("hiworld", "hiweb"));   // hiw
    }
}
